// Copyright 2017 the V8 project authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

#ifndef V8_MAP_UPDATER_H_
#define V8_MAP_UPDATER_H_

#include "src/elements-kind.h"
#include "src/field-type.h"
#include "src/globals.h"
#include "src/handles.h"
#include "src/objects/map.h"
#include "src/property-details.h"

namespace v8 {
namespace internal {

    // The |MapUpdater| class implements all sorts of map reconfigurations
    // including changes of elements kind, property attributes, property kind,
    // property location and field representations/type changes. It ensures that
    // the reconfigured map and all the intermediate maps are properly integrated
    // into the exising transition tree.
    //
    // To avoid high degrees over polymorphism, and to stabilize quickly, on every
    // rewrite the new type is deduced by merging the current type with any
    // potential new (partial) version of the type in the transition tree.
    // To do this, on each rewrite:
    // - Search the root of the transition tree using FindRootMap, remember
    //   the integrity level (preventExtensions/seal/freeze) transitions.
    // - Find/create a |root_map| with requested |new_elements_kind|.
    // - Find |target_map|, the newest matching version of this map using the
    //   "updated" |old_map|'s descriptor array (i.e. whose entry at |modify_index|
    //   is considered to be of |new_kind| and having |new_attributes|) to walk
    //   the transition tree. If there was an integrity level transition on the path
    //   to the old map, use the descriptor array of the map preceding the first
    //   integrity level transition (|integrity_source_map|), and try to replay
    //   the integrity level transition afterwards.
    // - Merge/generalize the "updated" descriptor array of the |old_map| and
    //   descriptor array of the |target_map|.
    // - Generalize the |modify_index| descriptor using |new_representation| and
    //   |new_field_type|.
    // - Walk the tree again starting from the root towards |target_map|. Stop at
    //   |split_map|, the first map who's descriptor array does not match the merged
    //   descriptor array.
    // - If |target_map| == |split_map|, and there are no integrity level
    //   transitions, |target_map| is in the expected state. Return it.
    // - Otherwise, invalidate the outdated transition target from |target_map|, and
    //   replace its transition tree with a new branch for the updated descriptors.
    // - If the |old_map| had integrity level transition, create the new map for it.
    class MapUpdater {
    public:
        MapUpdater(Isolate* isolate, Handle<Map> old_map);

        // Prepares for reconfiguring of a property at |descriptor| to data field
        // with given |attributes| and |representation|/|field_type| and
        // performs the steps 1-5.
        Handle<Map> ReconfigureToDataField(int descriptor,
            PropertyAttributes attributes,
            PropertyConstness constness,
            Representation representation,
            Handle<FieldType> field_type);

        // Prepares for reconfiguring elements kind and performs the steps 1-5.
        Handle<Map> ReconfigureElementsKind(ElementsKind elements_kind);

        // Prepares for updating deprecated map to most up-to-date non-deprecated
        // version and performs the steps 1-5.
        Handle<Map> Update();

    private:
        enum State {
            kInitialized,
            kAtRootMap,
            kAtTargetMap,
            kAtIntegrityLevelSource,
            kEnd
        };

        // Try to reconfigure property in-place without rebuilding transition tree
        // and creating new maps. See implementation for details.
        State TryReconfigureToDataFieldInplace();

        // Step 1.
        // - Search the root of the transition tree using FindRootMap.
        // - Find/create a |root_map_| with requested |new_elements_kind_|.
        State FindRootMap();

        // Step 2.
        // - Find |target_map|, the newest matching version of this map using the
        //   "updated" |old_map|'s descriptor array (i.e. whose entry at
        //   |modify_index| is considered to be of |new_kind| and having
        //   |new_attributes|) to walk the transition tree. If there was an integrity
        //   level transition on the path to the old map, use the descriptor array
        //   of the map preceding the first integrity level transition
        //   (|integrity_source_map|), and try to replay the integrity level
        //   transition afterwards.
        State FindTargetMap();

        // Step 3.
        // - Merge/generalize the "updated" descriptor array of the |old_map_| and
        //   descriptor array of the |target_map_|.
        // - Generalize the |modified_descriptor_| using |new_representation| and
        //   |new_field_type_|.
        Handle<DescriptorArray> BuildDescriptorArray();

        // Step 4.
        // - Walk the tree again starting from the root towards |target_map|. Stop at
        //   |split_map|, the first map who's descriptor array does not match the
        //   merged descriptor array.
        Handle<Map> FindSplitMap(Handle<DescriptorArray> descriptors);

        // Step 5.
        // - If |target_map| == |split_map|, |target_map| is in the expected state.
        //   Return it.
        // - Otherwise, invalidate the outdated transition target from |target_map|,
        //   and replace its transition tree with a new branch for the updated
        //   descriptors.
        State ConstructNewMap();

        // Step 6 (if there was
        // - If the |old_map| had integrity level transition, create the new map
        //   for it.
        State ConstructNewMapWithIntegrityLevelTransition();

        // When a requested reconfiguration can not be done the result is a copy
        // of |old_map_| where every field has |Tagged| representation and |Any|
        // field type. This map is disconnected from the transition tree.
        State CopyGeneralizeAllFields(const char* reason);

        // Returns name of a |descriptor| property.
        inline Name GetKey(int descriptor) const;

        // Returns property details of a |descriptor| in "updated" |old_descrtiptors_|
        // array.
        inline PropertyDetails GetDetails(int descriptor) const;

        // Returns value of a |descriptor| with kDescriptor location in "updated"
        // |old_descrtiptors_| array.
        inline Object GetValue(int descriptor) const;

        // Returns field type for a |descriptor| with kField location in "updated"
        // |old_descrtiptors_| array.
        inline FieldType GetFieldType(int descriptor) const;

        // If a |descriptor| property in "updated" |old_descriptors_| has kField
        // location then returns it's field type otherwise computes optimal field
        // type for the descriptor's value and |representation|. The |location|
        // value must be a pre-fetched location for |descriptor|.
        inline Handle<FieldType> GetOrComputeFieldType(
            int descriptor, PropertyLocation location,
            Representation representation) const;

        // If a |descriptor| property in given |descriptors| array has kField
        // location then returns it's field type otherwise computes optimal field
        // type for the descriptor's value and |representation|.
        // The |location| value must be a pre-fetched location for |descriptor|.
        inline Handle<FieldType> GetOrComputeFieldType(
            Handle<DescriptorArray> descriptors, int descriptor,
            PropertyLocation location, Representation representation);

        void GeneralizeField(Handle<Map> map, int modify_index,
            PropertyConstness new_constness,
            Representation new_representation,
            Handle<FieldType> new_field_type);

        bool TrySaveIntegrityLevelTransitions();

        Isolate* isolate_;
        Handle<Map> old_map_;
        Handle<DescriptorArray> old_descriptors_;
        Handle<Map> root_map_;
        Handle<Map> target_map_;
        Handle<Map> result_map_;
        int old_nof_;

        // Information about integrity level transitions.
        bool has_integrity_level_transition_ = false;
        PropertyAttributes integrity_level_ = NONE;
        Handle<Symbol> integrity_level_symbol_;
        Handle<Map> integrity_source_map_;

        State state_ = kInitialized;
        ElementsKind new_elements_kind_;
        bool is_transitionable_fast_elements_kind_;

        // If |modified_descriptor_| is not equal to -1 then the fields below form
        // an "update" of the |old_map_|'s descriptors.
        int modified_descriptor_ = -1;
        PropertyKind new_kind_ = kData;
        PropertyAttributes new_attributes_ = NONE;
        PropertyConstness new_constness_ = PropertyConstness::kMutable;
        PropertyLocation new_location_ = kField;
        Representation new_representation_ = Representation::None();

        // Data specific to kField location.
        Handle<FieldType> new_field_type_;

        // Data specific to kDescriptor location.
        Handle<Object> new_value_;
    };

} // namespace internal
} // namespace v8

#endif // V8_MAP_UPDATER_H_
